package org.example.myleet.boyermoorevoting;

public class BoyerMooreVotingSolution {

    //面试题 17.10. 主要元素
    /**
     * Boyer-Moore投票算法，时间复杂度O(n)，空间复杂度O(1)
     * Boyer-Moore 投票算法的步骤如下：
     *
     * 1、维护一个候选主要元素candidate和候选主要元素的出现次数count，初始时candidate为任意值，count=0；
     * 2、遍历数组nums 中的所有元素，遍历到元素x 时，进行如下操作：
     * （1）如果count=0，则将x 的值赋给candidate，否则不更新candidate 的值；
     * （2）如果x=candidate，则将count 加1，否则将count 减1。
     * 3、遍历结束之后，如果数组nums 中检查candidate元素确实数量过半，则candidate 即为主要元素，否则找不到主要元素。
     *
     * 参考：https://zhuanlan.zhihu.com/p/76518429
     */
    public int majorityElement(int[] nums) {
        if (nums.length < 1) {
            return -1;
        }
        int candidate = nums[0];
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            if (candidate == num) {
                ++count;
            } else {
                --count;
            }
        }
        count = 0;
        for (int num : nums) {
            if (num == candidate) {
                ++count;
            }
        }
        if (count > nums.length / 2) {
            return candidate;
        }
        return -1;
    }
}
